132 pattern

Time: O(N); Space: O(N); medium

Given a sequence of N integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that:

  • i < j < k and

  • ai < ak < aj.

Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Example 1:

Input: nums = [1, 2, 3, 4]

Output: False

Explanation:

  • There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3, 1, 4, 2]

Output: True

Explanation:

  • There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1, 3, 2, 0]

Output: True

Explanation:

  • There are three 132 patterns in the sequence:

[-1, 3, 2], [-1, 3, 0] and [-1, 2, 0]

1. Brute Force

The simplest solution is to consider every triplet (i, j, k)(i,j,k) and check if the corresponding numbers satisfy the 132 criteria. If any such triplet is found, we can return a True value. If no such triplet is found, we need to return a False value.

Complexity:

  • Time: O(n^3). Three loops are used to consider every possible triplet. Here, nn refers to the size of numsnums array.

  • Space: O(1). Constant extra space is used.

2. Better Brute Force

Algorithm

We can improve the last approach to some extent, if we make use of some observations. We can note that for a particular number nums[j] chosen as 2nd element in the 132 pattern, if we don’t consider nums[k] (the 3rd element) for the time being, our job is to find out the first element, nums[i] (i<ji<j) which is lesser than nums[j].

Now, assume that we have somehow found a nums[i],nums[j] pair. Our task now reduces to finding out a nums[k] (k>j>i), which falls in the range (nums[i], nums[j]). Now, to maximize the likelihood of a nums[k] falling in this range, we need to increase this range as much as possible.

Since, we started off by fixing a nums[j], the only option in our hand is to choose a minimum value of nums[i] given a particular nums[j]. Once, this pair (nums[i],nums[j]), has been found out, we simply need to traverse beyond the index j to find if a nums[k] exists for this pair satisfying the 132 criteria.

Based on the above observations, while traversing over the numsnums array choosing various values of nums[j], we simultaneously keep a track of the minimum element found so far (excluding nums[j]). This minimum element always serves as the nums[i] for the current nums[j]. Thus, we only need to traverse beyond the j-th index to check the nums[k]’s to determine if any of them satisfies the 132 criteria.

Complexity:

  • Time: O(n^2). Two loops are used to find the nums[j],nums[k] pairs. Here, nn refers to the size of numsnums array.

  • Space: O(1). Constant extra space is used.

3. Searching Intervals

Algorithm

As discussed in the last approach, once we’ve fixed a (nums[i],nums[j]) pair, we just need to determine a nums[k] which falls in the range (nums[i],nums[j]). Further, to maximize the likelihood of any arbitrary nums[k] falling in this range, we need to try to keep this range as much as possible. But, in the last approach, we tried to work only on nums[i]. But, it’ll be a better choice, if we can somehow work out on nums[j] as well.

To do so, we can look at the given numsnums array in the form of a graph, as shown below:

From the above graph, which consists of rising and falling slopes, we know, the best qualifiers to act as the (nums[i],nums[j]) pair, as discussed above, to maximize the range nums[i], nums[j] at any instant, while traversing the numsnums array, will be the points at the endpoints of a local rising slope. Thus, once we’ve found such points, we can traverse over the numsnums array to find a nums[k] satisfying the given 132 criteria.

To find these points at the ends of a local rising slope, we can traverse over the given numsnums array. While traversing, we can keep a track of the minimum point found after the last peak(nums[s]).

Now, whenever we encounter a falling slope, say, at index ii, we know, that nums[i-1] was the endpoint of the last rising slope found. Thus, we can scan over the kk indices(k>i), to find a 132 pattern.

But, instead of traversing over numsnums to find a kk satisfying the 132 pattern for every such rising slope, we can store this range (nums[s], nums[i-1]) (acting as (nums[i], nums[j])) in, say an intervalsintervals array.

While traversing over the numsnums array to check the rising/falling slopes, whenever we find any rising slope, we can keep adding the endpoint pairs to this intervalsintervals array. At the same time, we can also check if the current element falls in any of the ranges found so far. If so, this element satisfies the 132 criteria for that range.

If no such element is found till the end, we need to return a False value.

Complexity:

  • Time: O(n^2). We traverse over the numsnums array of size nn once to find the slopes. But for every element, we also need to traverse over the intervalsintervals to check if any element falls in any range found so far. This array can contain atmost (n/2)(n/2) pairs, in the case of an alternate increasing-decreasing sequence(worst case e.g. [5 6 4 7 3 8 2 9]).

  • Space: O(n). intervalsintervals array can contain atmost n/2n/2 pairs, in the worst case(alternate increasing-decreasing sequence).

4. Stack

Algorithm

In Approach 2, we found out nums[i] corresponding to a particular nums[j] directly without having to consider every pair possible in numsnums to find this (nums[i],nums[j]) pair. If we do some preprocessing, we can make the process of finding a nums[k] corresponding to this (nums[i],nums[j]) pair also easy.

The preprocessing required is to just find the best nums[i]nums[i] value corresponding to every nums[j] value. This is done in the same manner as in the second approach i.e. we find the minimum element found till the j-th element which acts as the nums[i] for the current nums[j]. We maintain thes values in a minmin array. Thus, min[j] now refers to the best nums[i] value for a particular nums[j].

Now, we traverse back from the end of the numsnums array to find the nums[k]’s. Suppose, we keep a track of the nums[k] values which can potentially satisfy the 132 criteria for the current nums[j]. We know, one of the conditions to be satisfied by such a nums[k] is that it must be greater than nums[i]. Or in other words, we can also say that it must be greater than min[j] for a particular nums[j] chosen.

Once it is ensured that the elements left for competing for the nums[k] are all greater than min[j] (or nums[i]), our only task is to ensure that it should be lesser than nums[j]. Now, the best element from among the competitors, for satisfying this condition will be the minimum one from out of these elements.

If this element, nums[min] satisfies nums[min] < nums[j], we’ve found a 132 pattern. If not, no other element will satisfy this criteria, since they are all greater than or equal to nums[min] and thus greater than or equal to nums[j] as well.

To keep a track of these potential nums[k] values for a particular (nums[i],nums[j]) considered currently, we maintain a stackstack on which these potential nums[k]’s satisfying the 132 criteria lie in a descending order(minimum element on the top). We need not sort these elements on the stackstack, but they’ll be sorted automatically as we’ll discuss along with the process.

After creating a minmin array, we start traversing the nums[j] array in a backward manner. Let’s say, we are currently at the j-th element and let’s also assume that the stackstack is sorted right now. Now, firstly, we check if nums[j] > min[j]. If not, we continue with the (j-1)-th element and the stackstack remains sorted. If not, we keep on popping the elements from the top of the stackstack till we find an element, stack[top] such that, stack[top] > min[j] (or stack[top] > nums[i]).

Once the popping is done, we’re sure that all the elements pending on the stackstack are greater than nums[i] and are thus, the potential candidates for nums[k] satisfying the 132 criteria. We can also note that the elements which have been popped from the stackstack, all satisfy stack[top] <= min[j].

Since, in the minmin array, min[p] <= min[q], for every p > qp>q, these popped elements also satisfy stack[top] <= min[k], for all 0 ≤ k < j. Thus, they are not the potential nums[k] candidates for even the preceding elements. Even after doing the popping, the stackstack remains sorted.

After the popping is done, we’ve got the minimum element from amongst all the potential nums[k]’s on the top of the stackstack (as per the assumption). We can check if it is greater than nums[j] to satisfy the 132 criteria(we’ve already checked stack[top] > nums[i]). If this element satisfies the 132 criteria, we can return a True value. If not, we know that for the current j, nums[j] > min[j]. Thus, the element nums[j] could be a potential nums[k] value, for the preceding nums[i]’s.

Thus, we push it over the stackstack. We can note that, we need to push this element nums[j] on the stackstack only when it didn’t satisfy stack[top] < nums[j]. Thus, nums[j] <= stack[top]. Thus, even after pushing this element on the stackstack, the stackstack remains sorted. Thus, we’ve seen by induction, that the stackstack always remains sorted.

Also, note that in case nums[j] <= min[j], we don’t push nums[j] onto the stackstack. This is because this nums[j] isn’t greater than even the minimum element lying towards its left and thus can’t act as nums[k] in the future.

If no element is found satisfying the 132 criteria till reaching the first element, we return a False value.

See also: https://leetcode.com/problems/132-pattern/solution/

Complexity:

  • Time: O(n). We travesre over the numsnums array of size nn once to fill the minmin array. After this, we traverse over numsnums to find the nums[k]. During this process, we also push and pop the elements on the stackstack. But, we can note that atmost nn elements can be pushed and popped off the stackstack in total. Thus, the second traversal requires only O(n) time.

  • Space: O(n). The stackstack can grow upto a maximum depth of nn. Furhter, minmin array of size nn is used.

6. Using Array as a Stack

Algorithm

In the last approach, we’ve seen that in the worst case, the required element won’t be found for all the nn elements and thus Binary Search is done at every step increasing the time complexity.

To remove this problem, we can follow the same steps as in Approach 4 i.e. we can remove those elements(update the index k) which aren’t greater than nums[i] (min[j]).

Thus, in case no element is larger than min[j] the index k reaches the last element.

Now, at every step, only nums[j] will be added and removed from consideration in the next step, improving the time complexity in the worst case. The rest of the method remains the same as in Approach 4.

Complexity:

  • Time: O(n). We travesre over the nums array of size nn once to fill the minmin array. After this, we traverse over numsnums to find the nums[k]. Atmost n elements can be put in and out of the nums array in total. Thus, the second traversal requires only O(n) time.

  • Space: O(n). Min array of size n is used.

[6]:

class Solution1(object):
    def find132pattern(self, nums) -> bool:
        """
        :type nums: List[int]
        :rtype: bool
        """
        ak = float("-inf")
        st = []
        for i in reversed(range(len(nums))):
            if nums[i] < ak:
                return True
            else:
                while st and nums[i] > st[-1]:
                    ak = st.pop()
            st.append(nums[i])
        return False

[7]:

s = Solution1()
nums = [1, 2, 3, 4]
assert s.find132pattern(nums) == False
nums = [3, 1, 4, 2]
assert s.find132pattern(nums) == True
nums = [-1, 3, 2, 0]
assert s.find132pattern(nums) == True